package org.liaohailong.helloworld.hash;

/**
 * Author: liaohailong
 * Date: 2021/5/21
 * Time: 20:40
 * Description:
 **/
public class MyHashSet {

//    private static final int MAXIMUM_CAPACITY = 1 << 30;
//
//    private static int tableSizeFor(int cap) {
//        int n = cap - 1;
//        n |= n >>> 1;
//        n |= n >>> 2;
//        n |= n >>> 4;
//        n |= n >>> 8;
//        n |= n >>> 16;
//        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
//    }
//
//    final int[] bucket;
//
//    /**
//     * Initialize your data structure here.
//     */
//    public MyHashSet() {
//        int cap = tableSizeFor(1000000);
//        bucket = new int[cap];
//        Arrays.fill(bucket, -1);
//    }
//
//    private int indexFor(int key) {
//        int n = bucket.length - 1;
//        return key & n;
//    }
//
//    public void add(int key) {
//        int index = indexFor(key);
//        bucket[index] = key;
//    }
//
//    public void remove(int key) {
//        int index = indexFor(key);
//        bucket[index] = -1;
//    }
//
//    /**
//     * Returns true if this set contains the specified element
//     */
//    public boolean contains(int key) {
//        int index = indexFor(key);
//        return bucket[index] != -1;
//    }

    final int size = 1024;
    final Node[] bucket;

    /**
     * Initialize your data structure here.
     */
    public MyHashSet() {
        bucket = new Node[size];
    }

    private int index(int key) {
        return key % size;
    }

    public void add(int key) {
        if (contains(key)) return;

        int index = index(key);
        Node node = bucket[index];
        if (node == null) {
            node = new Node(key);
            bucket[index] = node;
        } else {
            last(node).next = new Node(key);
        }
    }

    private Node last(Node head) {
        Node node = head;
        while (node.next != null) node = node.next;
        return node;
    }

    public void remove(int key) {
        int index = index(key);
        Node node = bucket[index];
        if (node == null) return;
        node = remove(node, key);
        bucket[index] = node;
    }

    private final Node empty = new Node(-1);

    private Node remove(Node head, int key) {
        empty.next = head;
        Node node = empty;
        while (node != null && node.next != null) {
            if (node.next.val == key) node.next = node.next.next;
            node = node.next;
        }
        Node next = empty.next;
        empty.next = null;
        return next;
    }

    /**
     * Returns true if this set contains the specified element
     */
    public boolean contains(int key) {
        int index = index(key);
        Node node = bucket[index];
        if (node == null) return false;
        return find(node, key);
    }

    private boolean find(Node head, int key) {
        empty.next = head;
        Node node = empty;
        while (node.next != null) {
            if (node.next.val == key) return true;
            node = node.next;
        }
        empty.next = null;
        return false;
    }

    private static final class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }
}
